package demo;

import java.util.Deque;
import java.util.LinkedList;


public class PreOrder {
    //构建二叉树
    public static TreeNode buildTree(){
        TreeNode n1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3=new TreeNode(3);
        TreeNode n4=new TreeNode(4);
        TreeNode n5=new TreeNode(5);
        TreeNode n6=new TreeNode(6);
        TreeNode n7=new TreeNode(7);

        n1.left=n2; n1.right=n3;
        n2.left=n4; n2.right=n5;
        n3.left=n6; n3.right=n7;

        return n1;

    }
    //二叉树前序遍历非递归
    private static void preOrder(TreeNode root){
        TreeNode cur=root;
        Deque<TreeNode> stack=new LinkedList<>();

        while(cur!=null||!stack.isEmpty()){

            while(cur!=null){
                System.out.println(cur.val);
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            if(top.right!=null){
                cur=top.right;
            }
        }
    }
    //二叉树中序非递归实现
    private static void inOrder(TreeNode root){
        Deque<TreeNode> stack2=new LinkedList<>();
        TreeNode cur=root;
        while(cur!=null||!stack2.isEmpty()){
            while(cur!=null){
                stack2.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack2.pop();
            System.out.println(top.val);
            if(top.right!=null){
                cur=top.right;
            }

        }
    }




    public static void main(String[] args) {
        TreeNode root=buildTree();
        preOrder(root);
        System.out.println("---------------");
        inOrder(root);
        System.out.println("------------");
    }

}
